Search for: All records

We study monotone cellular automata (also known as ‐bootstrap percolation) in with random initial configurations. Confirming a conjecture of Balister, Bollobás, Przykucki and Smith, who proved the corresponding result in two dimensions, we show that the critical probability is non‐zero for all subcritical models.

In its usual form, Freiman's theorem states that if and are subsets of of size with small sumset (of size close to ), then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this by allowing only a bounded number of possible summands from one of the sets. We show that if and are subsets of of size such that for any four‐element subset of the sumset has size not much more than , then already this implies that and are very close to arithmetic progressions.

In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs onwith m edges, wheneverand. We give an asymptotic formula for the numberof connected r‐uniform hypergraphs onwith m edges, wheneveris fixed andwith, that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case) and the present authors (the case, ie, “nullity” or “excess”o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.